//https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
class Solution {
public:
    int BinarySearch(const vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] > target)
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                return mid;
        }

        return -1;
    }

    vector<int> twoSum(vector<int>& price, int target) {
        vector<int> ret;

        for (int i = 0; i < price.size(); i++)
        {
            int search = BinarySearch(price, target - price[i]);
            //cout<< i << " "<<search<<endl;
            if (search >= 0)
            {
                ret.push_back(price[i]);
                ret.push_back(price[search]);
                return ret;
            }
        }

        return ret;
    }
};